
#include <math.h>
#include <stdio.h>

#include "globals.h"
#include "geometry.h"
#include "polygon.h"
#include "voronoi.h"
#include "distance.h"
#include "sgidrawi.h"
#include "sweep.h"


/*
   *********************************************************************
   *********************************************************************
*/

#define	CantHappen	0
#define OnFirstEnd	1
#define OnSecondEnd	2
#define OnSegment	3

int
pplTest (Pgon **pgonList, int *startIdx, int lineIdx)
{
	int		answer = CantHappen;
	Line	ptBisect, ptLine, line, endPerp[2];
	Pt		intPt[2], checkPt;
	Pt		*segPt1, *segPt2, *pt1, *pt2;

	pt1 = &(pgonList[(lineIdx + 1)%3]->points[startIdx[(lineIdx + 1)%3]]);
	pt2 = &(pgonList[(lineIdx + 2)%3]->points[startIdx[(lineIdx + 2)%3]]);
	segPt1 = &(pgonList[lineIdx]->points[startIdx[lineIdx]]);
	segPt2 = &(pgonList[lineIdx]->points[(startIdx[lineIdx] + 1) % 
				pgonList[lineIdx]->numPoints]);

	/*	Get the line bisecting the two points, the line segment
		itself, and the lines perpendicular to each of the segment's
		endpoints. */

	LineOf (pt1, pt2, &ptLine);
	pointBisector(pt1, pt2, &ptBisect);

	LineOf (segPt1, segPt2, &line);

	perpRightTurnLine (segPt1, &line, &(endPerp[0]));
	perpRightTurnLine (segPt2, &line, &(endPerp[1]));

	/*	Intersect the bisector of the two points with the 
		perpendicular lines to the segment. */

	IntersectionOf(&ptBisect, &(endPerp[0]), &(intPt[0]));
	IntersectionOf(&ptBisect, &(endPerp[1]), &(intPt[1]));

	if (PointAtInfinity(intPt[0]) || PointAtInfinity(intPt[1])) {
		IntersectionOf(&ptBisect, &line, &checkPt);
		if (nearestPointOnSegment(&checkPt, segPt1, segPt2) == True)
			answer = OnSegment;
		else {
			Real	d0, d1;

			squarePointDistance(&(checkPt), segPt1, &d0);
			squarePointDistance(&(checkPt), segPt2, &d1);
			if (d0 < d1)
				answer = OnFirstEnd;
			else
				answer = OnSecondEnd;
		}
	}
	else {
		/*	Make sure that the two points are on the same side of the
			segment. */

		IntersectionOf(&ptLine, &line, &checkPt);
		if ((nearestPointOnSegment(&checkPt, segPt1, segPt2) == True) &&
			(nearestPointOnSegment(&checkPt, pt1, pt2) == True)) {
			if (SamePoint(&checkPt, pt1) || SamePoint(&checkPt, pt2))
				answer = OnSegment;
			else
				answer = CantHappen;
		}
		else {
			Real	ptDist[2], segDist[2];

			/*	Work with the distances from the intPts to the segment's
				endpoints and to one of the other points. */

			squarePointDistance(&(intPt[0]), pt1, &(ptDist[0]));
			squarePointDistance(&(intPt[1]), pt1, &(ptDist[1]));

			squarePointDistance(&(intPt[0]), segPt1, &(segDist[0]));
			squarePointDistance(&(intPt[1]), segPt2, &(segDist[1]));

			if ((LineSide(&(endPerp[0]), pt1) == LineSide(&(endPerp[1]),pt1)) ||
				(LineSide(&(endPerp[0]), pt2) == LineSide(&(endPerp[1]), pt2))){

				/*	At least one of the points is on the same side of
					both perpendicular lines. */

				if ( ( (Less (ptDist[0], segDist[0])) && 
							(Greater (ptDist[1], segDist[1])) ) ||
					 ( (Greater (ptDist[0], segDist[0])) && 
							(Less (ptDist[1], segDist[1])) ) ) {
					answer = OnSegment;
				}
				else if (Less (ptDist[0], segDist[0])) {
					answer = ( Greater(segDist[0], segDist[1]) ? 
								OnFirstEnd : OnSecondEnd);
				}
				else {
					answer = ( Less(segDist[0], segDist[1]) ? 
								OnFirstEnd : OnSecondEnd);
				}
			}
			else {
				boolean	ccwOrder[2];

				ccwOrder[0] = pointsCCW( pt1, pt2, segPt1 );
				ccwOrder[1] = pointsCCW( pt1, pt2, segPt2 );

				/*	Both points have their nearest points to the segment
					actually on the segment itself. */

				if ( (Greater(ptDist[0], segDist[0])) && 
						(Greater(ptDist[1], segDist[1])) ) {
					answer = OnSegment;
				}
				else if (ccwOrder[0] && !ccwOrder[1]) {
					answer = OnFirstEnd;
				}
				else if (!ccwOrder[0] && ccwOrder[1]) {
					answer = OnSecondEnd;
				}
				else {
					answer = ( Less(segDist[0], segDist[1]) ?
								OnFirstEnd : OnSecondEnd);
				}
			}
		}
	}

	return (answer);
}

int
pllTest (Pgon **pgonList, int *startIdx)
{
	return (0);
}

/*
   *********************************************************************
   *********************************************************************
*/

void
recordPolygonInSet (Pgon *a, int *signature)
{
	if (a->numPoints == 1) 
		signature[0] += 1;
	else if (a->numPoints == 2)
		signature[1] += 1;
	else 
		signature[2] += 1;
}

void
identifyPolygonSet (Pgon *a, Pgon *b, Pgon *c, int *signature)
{
	signature[0] = 0;
	signature[1] = 0;
	signature[2] = 0;

	recordPolygonInSet (a, signature);
	recordPolygonInSet (b, signature);
	recordPolygonInSet (c, signature);
}

int
orderPtsAndLines (Pgon **list, int *signature)
{
	int pos;

	if ((signature[0] == 2) && (signature[1] == 1)) {
		/*	Put the one line last in the array. */

		if (list[0]->numPoints == 2) 
			pos = 0;
		else if (list[1]->numPoints == 2) 
			pos = 1;
		else 
			pos = 2;
	}
	else if ((signature[0] == 1) && (signature[1] == 2)) {
		/*	Put the one point first in the array. */

		if (list[0]->numPoints == 1) 
			pos = 0;
		else if (list[1]->numPoints == 1) 
			pos = 1;
		else 
			pos = 2;
	}
	else {
		/*	Either three points or three lines where any order will do
			or I can't determine an order right now -- deal with it later.  */

		pos = 0;
	}

	return (pos);
}


/*	I assume that all three poygons are distinct from one another 
	as we enter this routine. */

#define vorName voronoiVertex

boolean
vorName(Pgon *a, Pgon *b, Pgon *c, Pt *vorPoint, Pt *eventPoint, 
	spokeInfo *middleSpoke)
{
	int			signature[3];
	boolean		ccw;
	Pgon		*ordered[3];
	int			startIdx[3], oddStart;

#ifdef DEBUG_VORONOI
	printf ("vor: compute Voronoi vertex\n");
#endif

	ordered[0] = a; ordered[1] = b; ordered[2] = c;
	startIdx[0] = 0; startIdx[1] = 0; startIdx[2] = 0;

	/*	Find out what the "polygons" look like -- are we just dealing
		with points, lines, polygons, or some mixture? */

	identifyPolygonSet (a,b,c, signature);

	/*	We can find the configuration we have by looking at the signature. 
		Possible cases are:  
			ppp, ppl, pll, plP, ppP, pPP, lll, llP, lPP, PPP */

	if (signature[0] == 3) {
		/*	Simple case where we are dealing with three points */
		ccw = pppVoronoi (ordered, startIdx, vorPoint, eventPoint, 
				middleSpoke);
	}
	else if ((signature[0] == 2) && (signature[1] == 1)) {
		oddStart = orderPtsAndLines (ordered, signature);
#if 1
			ccw = pplVoronoi (ordered, startIdx, oddStart, vorPoint, 
					eventPoint, middleSpoke);
#else
		switch (pplTest (ordered, startIdx, oddStart)) {
		case OnFirstEnd:
			ccw = pppVoronoi (ordered, startIdx, vorPoint, eventPoint,
					middleSpoke);
			break;
		case OnSecondEnd:
			startIdx[2] = (startIdx[2] + 1) % (ordered[2]->numPoints);
			ccw = pppVoronoi (ordered, startIdx, vorPoint, eventPoint,
				middleSpoke);
			break;
		case OnSegment:
			ccw = pplVoronoi (ordered, startIdx, oddStart, vorPoint, 
					eventPoint, middleSpoke);
			break;
		default:
			ccw = False;
			break;
		}
#endif
	}
	else if ((signature[0] == 1) && (signature[1] == 2)) {
		oddStart = orderPtsAndLines (ordered, signature);
		ccw = pllVoronoi (ordered, startIdx, oddStart, vorPoint, 
				eventPoint, middleSpoke);
	}
	else if (signature[1] == 3) {
		ccw = lllVoronoi (ordered, startIdx, vorPoint, eventPoint,
				middleSpoke);
	}
	else {
		printf ("Kaboom!  Don't know how to compute the "
			"Voronoi vertex yet.\n");
		printf ("signature was %d %d %d\n", signature[0], signature[1],
			signature[2]);
		ccw = False;
	}

	return (ccw);
}

